#pragma once
#define _USE_MATH_DEFINES
#include <string>
#include <iostream>
#include <complex>
#include <math.h>

#include "targetver.h"
#include <windows.h>

#include <stdio.h>
#include <tchar.h>
#include <time.h>
#include <list>
#include <vector>
#include <algorithm>
#include <queue>
#include <string>

#include <mpi.h>

using namespace std;

// Short dwarf's description.
#define DWARF_NAME (char*)"Branch and Bound, unmanaged mpi kernel."

// Constants for output files's names
#define DWARF_NAME_OUTPUT (char*)"Dwarf.Unmanaged.Mpi"
#define NUMBER_ROOT_PROCESS 0                       // index of root process.
#define PROFILE_TXT (char*)".Profile.txt"
#define RESULT_TXT (char*)".Result.txt"

// Default size for buffer.
#define BUFFER_SIZE 1024

//Parse the command line arguments and fill the reference parameters.
typedef int (__cdecl *DLLParseArguments)(
   int,                                    //Count of command line tokens.
   char**,                                 //Command line tokens.
   char**,                                 //Name of input text file.
   char**,                                 //Name of profile text file.
   char** );                               //Name of result file.

// Write the rules of command line structure.
typedef void (__cdecl *DLLUsage)(void);

// Start the time count.
typedef void (__cdecl *DLLStart)(void);

// Stop the time count.
typedef void (__cdecl *DLLStop)(double*);


// Assignment problem that is the relaxed version of the TSP problem
class AssignmentProblem;
class BranchingInformation;
class Solver;

typedef enum SolutionType { 
    // The solution is a single loop and is exact under the given constraints.
    ExactSolution,
    // The lower bound for the solution was greater than the upper bound,
    // so the solution was pruned.
    PrunedSolution,
    // The lower bound was low enough, and the solution was patched 
    // using the Karp-Steele patching algorithm.
    PatchedSolution
} SolutionType;

typedef enum  {
    MpiProblemMessage,
    MpiSolutionMessage,
    MpiBranchesMessage,
} MPIMessageType;


class BranchingInformation {
public:
	BranchingInformation();
	BranchingInformation(int cityCount, int *fixedBuffer, int *variableBuffer);
	~BranchingInformation();

	int *fixedBuffer;
	int *variableBuffer;

    int cityCount;                          // count of points
    
	__int64 LowerBound;
    int* ToCities;
    int* FromCities;
    int* ConstraintMap;
    int* Exclusions;
	int exclusionsCount;
    int* u;
    int* v;

	int CycleCount;

    int getCount() { return childCount; }
    int GetExcludedRow(int childIndex) { return childFromCities[childIndex]; }

    bool operator<(BranchingInformation &y) {
        if (LowerBound < y.LowerBound)
            return true;
        if (LowerBound > y.LowerBound)
            return false;
        if (getCount() < y.getCount())
            return true;
        if (getCount() > y.getCount())
            return false;
        return false;
    }

	void Send(int destination);
    static BranchingInformation* Receive(int cityCount, int source);
    void GetChildConstraints(int childIndex, int* constraintMap, int*& exclusions, int &exclusionsCount);
	AssignmentProblem* GetProblem(int** distances, int childIndex, __int64 upperBound);
	void SendProblem(int childIndex, __int64 upperBound, int destination);

private:
    int* originalConstraintMap;

	int childCount;
    int* childFromCities;
    int* childToCities;

	void Include(int* constraintMap, int from, int to);
	void Exclude(int cityCount, int* constraintMap, int* exclusions, int &exclusionsCount, int from, int to);
};

typedef struct Cycle {
    int StartNode;   // First city in the cycle
    int Length;      // Total # cities
    int FreeLength;  // # cities not in the Include list
	bool operator<(struct Cycle &b) { return Length < b.Length; }
} Cycle;

class AssignmentProblem {
private:
	bool isRoot;
    static const int infinity = MAXINT;

    // Problem definition
    int cityCount;                          // count of points
    int** distances;                       // square matrix of distances between all points

	int* fixedBuffer;
    int* constraintMap;
    // constraintMap[i] >  0 -> (i, constraintMap[i]-1) is Included
    // constraintMap[i] == 0 -> no constraints on (i, ?)
    // constraintMap[i] <  0 -> -1 - constraintMap[i] = index of first element in exclusions list.
    int* exclusions;
    // See constraintMap. List is terminated by -1.
	int exclusionsCount;
	int exclusionsLength;

	// Solution:
	// Assignment problem
    int* toCities;               // destination city
    int* fromCities;             // originating city
    // Dual variables
    int* u;
    int* v;
    __int64 lowerBound;             // lower bound from assignment problem
	__int64 upperBound;			 // current best upper bound
	__int64 patchedValue;			 // total distance after patching
	int excludedRow;			 // index of originating city that is excluded
								 // relative to the parent.

	// Patched problem
	int* patchedToCities;		// destination city
    int* patchedFromCities;     // originating city


public:
    AssignmentProblem(int cityCount, int** distances);
	AssignmentProblem(int cityCount, int** distances, int* fixedBuffer, int* variableBuffer);
	~AssignmentProblem();
	static AssignmentProblem* Receive(int cityCount, int** distances, int source);

    __int64 getLowerBound() const { return lowerBound; }
    __int64 getValue() { return patchedValue; }
    void GetCities(int*);

    __int64 Solve(); 

    int AssignmentProblem::getCycleCount() const { return cycles.size(); }
    int AssignmentProblem::getChildCount() const { return cycles[minCycle].FreeLength; }

	__int64 Patch(class Solver* solver);

    void SendPrunedSolution(int destination);
    void SendExactSolution(int destination);
    void SendPatchedSolution(int destination);

	BranchingInformation* GetBranchingInformation();

private:
    bool IsAllowed(int row, int column);
    bool IsAllowedConstraint(int value, int column);
    void Include(int from, int to);
	void Exclude(int from, int to);
    bool SolveFromScratch();
    bool SolveIncremental();

    // We keep these as instance variables
    int* pathOrigins;
    int* reducedCosts;
    int* labeledRow;
    int* unlabeledColumn;
	void Dump(int* a);
    void AllocateAugmentingPathTemporaries();
    void FreeAugmentingPathTemporaries();
    void FindAugmentingPath(int row);

	std::vector<Cycle> cycles;
    int minCycle;

    void ComputeCycles();

    void Patch(int from, int to, int from2, int to2);
    __int64 Patch(int startCity, int startCity2);

    int* childFromCities;
    int* childToCities;
};

class Solver
{
public:
	Solver();
	~Solver();
	int Solve();
	void Finish(double time);
	__int64 getUpperBound() { return this->upperBound; }
	void ProcessMessages(bool wait);
    bool isRootThread;              //true for master process

	__int64 totalNodes;
    int cityCount;                           // count of points
	int* bestCities;
    int **distances;                         // square matrix of distances between all points
    static const int infinity = MAXINT;

private:

	// MPI
	int rank;								 // rank of process (MPI)
    int commsize;							 // process size
    static const int root = 0;				 // index of root process. By consideration, equal to 0
	MPI_Status status;						 // MPI status for receiving data

    SolutionType Solve(AssignmentProblem* problem);

	// Root specific
    __int64 upperBound;
    list<AssignmentProblem*> problemList;
    list<BranchingInformation*> solvedList;
    AssignmentProblem *best;


    void AddSolvedProblem(AssignmentProblem *problem);
    AssignmentProblem *NextSolvedProblem();

    bool* idle;
    int activeNodes;
    BranchingInformation *currentBranchingInfo;
    int currentBranchingIndex;

    AssignmentProblem* GetNextProblem();
    void SendNextProblem(int destination);
    bool MoreProblems(bool wait);
    void AddBranchingInformation(BranchingInformation* info);
    void SolveRoot();

    // Node specific
    void SolveNode();
};

// Short dwarf's description.
#define DWARF_NAME (char*)"Branch and Bound, unmanaged mpi kernel."

// Settings taken from command line and input file.
class Settings
{
public:
   Settings();
   ~Settings();

   void finish(Solver *solver);
   void start();
   int init(int argc, char** argv, Solver *solver);

private:
	static const int infinity = MAXINT;
   // Input & output files.
   char* inputFile;
   char* profileFile;
   char* resultFile;

   int parseConfigFile(Solver* solver);    // Parse input file into solver's structures.
   void writeSettings(Solver* solver);     // Write settings.
}; 